package algocasts;

public class P109_FindFirstAndLastPositionOfElementInSortedArray {
    public int[] searchRange(int[] nums, int target) {
        if (nums == null || nums.length == 0) return new int[]{-1, -1};
        int n = nums.length, start = -1, end = -1;
        for (int i = 0; i < n; i++)
            if (nums[i] == target) {
                start = i;
                break;
            }
        for (int i = n - 1; i >= 0; i--)
            if (nums[i] == target) {
                end = i;
                break;
            }
        return new int[]{start, end};
    }


    private int binarySearchLastOne(int[] nums, int target) {
        int low = 0, high = nums.length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (nums[mid] > target) high = mid - 1;
            else low = mid + 1;
        }
        return high;
    }

    public int[] searchRange_BinarySearch(int[] nums, int target) {
        if (nums == null || nums.length == 0) return new int[]{-1, -1};
        int end = binarySearchLastOne(nums, target);
        int start = binarySearchLastOne(nums, target - 1) + 1;
        if (start >= 0 && start <= end && end < nums.length)
            return new int[]{start, end};
        else return new int[]{-1, -1};
    }
}
